#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
public:
	int minPathSum(vector<vector<int>>& grid) {
		int m = grid.size(), n = grid[0].size();
		vector <vector<int>> res(m);
		for (auto& e : res)
		{
			e.resize(n);
			for (int f : e)
			{
				f = 0;
			}
		}

		for (int i = 0; i < m; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				if (i - 1 >= 0 && j - 1 >= 0)
				{
					res[i][j] = grid[i][j] + min(res[i - 1][j], res[i][j - 1]);
				}
				else if (i - 1 >= 0)
				{
					res[i][j] = grid[i][j] + res[i - 1][j];
				}
				else if (j - 1 >= 0)
				{
					res[i][j] = grid[i][j] + res[i][j - 1];
				}
				else
				{
					res[i][j] = grid[i][j];
				}
			}
		}

		return res[m - 1][n - 1];
	}
};
int main()
{
	//vector<vector<int> >v = { {1,3,1} ,{1,5,1},{4,2,1} };
	vector<vector<int> >v = { {1,2,3 }, { 4,5,6 } };

	cout << Solution().minPathSum(v) << endl;

	return 0;
}